1. Field of the Invention
Many devices may be described as finite state machines, i.e., as a finite set of states together with rules for getting from one state to another. Typically, a transition from one state to another occurs in response to an input to the device and results in an output from the device. Implementations of finite state machines require memory elements for storing the current state of the finite state machine.
A problem in the design of implementations of finite state machines is testing. The behavior of a finite state machine depends not only on the inputs to the machine, but also on the current state of the machine, as determined by the contents of the memory elements. Consequently, a finite state machine is fully testable only if all of the memory elements can be set and read.
2. Description of the Prior Art
There are two ways of designing circuits for testability. In one method, the designer follows certain ad hoc rules of testability. Since these rules are based on experience, one can hope that the final product will be testable although no guarantee is given. In the second method, after the design is completed, the circuit structure is augmented for testability. This added hardware tunes the circuit for a guaranteed test generation by some given method. For example, in scan design, the added hardware guarantees the use of a combinational circuit test generator. In some cases, however, adding hardware to an already designed circuit is considered undesirable. This may be particularly true when the design has undergone optimization.
The current state of the art in synthesis for logic and timing optimization appears to be more advanced than that in synthesis for testability as described in
A. J. de Geus, "Logic Synthesis Speeds ASIC Design", IEEE Spectrum, Vol. 26, pp. 27-31, August 1989, PA1 F. C. Hennie, "Fault Detecting Experiments for Sequential Circuits", Proc. 5th Annual Symp. on Switching Theory and Logical Design, Princeton University, pp. 95-110, November 1964 PA1 Z. Kohavi and P. Lavallee, "Design of Sequential Machines with Fault-Detection Capabilities" IEEE Trans. Electronic Computers, Vol. EC-16, pp. 473-484, August 1967, PA1 H. Fujiwara et al, "Easily Testable Sequential Machines with Extra Inputs", IEEE Trans. Comput., Vol. C-24, pp. 821-826, August 1975, PA1 V. D. Agrawal et al, "Automation in Design for Testability", Proc. custom Integrated Circuits Conf., Rochester, N.Y., pp. 159-163, May 1984.
Testing of finite state machines (FSM) was addressed by Hennie as described in
who devised checking experiments. In a checking experiment, an input sequence is applied to the machine such that the output uniquely distinguishes the machine from all other machines having the same number of inputs and outputs, and the same or fewer states. Hennie's procedure of constructing an input sequence for checking experiment is only practical when a distinguishing sequence exists. For an n-state machine, its distinguishing sequence (DS) will produce n different outputs depending upon the initial state. Kohavi and Lavallee identified the existence of a distinguishing sequence of bounded length as the requirement for diagnosability as described in
Their design for testability added an extra output to make the DS shorter. As described in
Fujiwara et al further defined an easily testable n-state machine as one having synchronizing and transfer sequences of length log.sub.2 n. A synchronizing sequence is defined as an input sequence whose application is guaranteed to leave the FSM in a certain final state regardless of its initial state. A transfer sequence is an input sequence that changes the state from a given initial state to a given final state.
For most practical FSMs, the procedures just mentioned tend to produce long sequences. Though useful in simulation-based design verification, such tests are not commonly used in production testing. The testing problem, thus, relates to finding a set of tests for modeled (usually, stuck type) faults. A commonly used design for testability is the scan method that converts the FSM testing problem to that of combinational logic testing, as described in
In the scan method, as well as in many other methods, the circuit is modified after the design is completed. With tool-based synthesis, the advantage of logic optimization may be lost in such post-design modification.
An object of the present invention is to overcome the just-described problems by providing a new method of synthesis of devices describable as finitestate machines which adds the test function before synthesis and by providing devices produced by the new method.